from functools import cache
from typing import List

# 记忆化搜索

class Solution:
    def findMaxForm(self, strs: List[str], m: int, n: int) -> int:

        # 二维费用背包
        n0 = len(strs)

        @cache
        # 0 1 组合  对于当前元素 同样 选 or 不选 问题
        def dfs(i, cnt0, cnt1):

            # 递归结束条件
            if i < 0:
                # 不需要返回1 因为 已经在 dfs的时候处理了 +1
                return 0
            # 分别统计 0 1 的个数
            count_0 = strs[i].count('0')
            count_1 = strs[i].count('1')

            if cnt0 >= count_0:
                if cnt1 >= count_1:
                    # 选（背包要减去选的权值）+1（子集）   不选
                    return max(dfs(i - 1, cnt0, cnt1), dfs(i - 1, cnt0 - count_0, cnt1 - count_1) + 1)
            # 不选
            return dfs(i - 1, cnt0, cnt1)

        return dfs(n0 - 1, m, n)

